package com.lxl.count;

import java.util.Arrays;

/**
 * @Description 计数排序
 * @Date 2021/8/24 20:54
 * @Created by LXLDEMO
 */
public class CountSort {
    public static void main(String[] args) {
        // 测试数据
        int arr[] = {37,18,21,21,49,0,25,6,14};
        countSort1(arr,arr.length);
    }


    /**
     * 计数排序
     * @param arr
     * @param len
     */
    public static void countSort1(int[] arr,int len){
        // 求取最大值最小值，确定桶区间范围
        // 记录数组中的最大值
        int max = Integer.MIN_VALUE;
        // 记录数组中的最小值
        int min = Integer.MAX_VALUE;
        for (int i = 0;i<len;i++){
            max = Math.max(max,arr[i]);
            min = Math.min(min,arr[i]);
        }
        System.out.println("最大值："+max);
        System.out.println("最小值："+min);

        // 长度为max的话，min如果是负数或者0的时候，下面的help[mapPos]会越界
//        int help[] = new int[max];

        // 辅助数组
        int help[] = new int[max-min+1];


        // 找出每个数字出现的次数
        for (int i = 0;i<len;i++){
            int mapPos = arr[i] - min;
            help[mapPos]++;
        }

        int index = 0;
        for (int i = 0;i<help.length;i++){
            while (help[i]-->0){
                arr[index++] = i+min;
            }
        }
        System.out.println("排序结果："+ Arrays.toString(arr));
    }


}
